﻿namespace SmallGeo;

internal static class TriangleAlg
{
    /// <summary>
    /// 注释参照: <seealso cref="Util.Triangle(List{Vector2d})"/>
    /// </summary>
    internal static List<int> Triangle(List<Vector2d> polygon)
    {
        var triangles = new List<int>();
        if (polygon == null || polygon.Count == 0) return triangles;
        var len = polygon.Count;
        if (polygon.Last() == polygon.First())
        {
            len--;
            polygon = polygon.Take(len).ToList();
        }

        //不是正常的三角形 所有点都在一条直线上?
        var area = Util.GetSignedArea(polygon);
        if (area == 0) return triangles;
        var isCCW = area > 0;

        var idxes = new List<int>();
        for (int j = 0; j < len; j++) idxes.Add(j);
        var i = 0;
        while (len > 2)
        {
            if (len == 3)
            {
                triangles.AddRange(new int[] { idxes[i], idxes[(i + 1) % len], idxes[(i + 2) % len] });
                break;
            }
            var a = polygon[idxes[i]];
            var b = polygon[idxes[(i + 1) % len]];
            var c = polygon[idxes[(i + 2) % len]];
            if (Util.Cross(a, b, c) == 0)
            {
                //共线
                i = (i + 1) % len;
                continue;
            }
            if (IsEar(a, b, c, polygon) && Util.IsCounterClockWise(new List<Vector2d> { a, b, c }) == isCCW)
            {
                //是多边形的耳朵, 且和多边形同时针
                triangles.AddRange(new int[] { idxes[i], idxes[(i + 1) % len], idxes[(i + 2) % len] });
                idxes.RemoveAt((i + 1) % len);
                if (i > (i + 1) % len)
                {
                    // 0 1 2 3 当前 i=3, 移除了0 此时 i 应变为 2
                    i--;
                }
                len--;
            }
            else
            {
                i = (i + 1) % len;
            }
        }
        return triangles;
    }

    /// <summary>
    /// 判断三个点是多边形 polygon 的耳朵,如: 下面的任意连续三点都是多形性的耳朵
    /// <code>
    /// 3-----2
    /// |     |
    /// |     |
    /// 0-----1
    /// </code>
    /// <br/>
    /// 而下面 0->1->2 不是多边形的耳朵, 因为 3 在 0->1->2 中
    /// <code>
    ///                  2
    ///                 **
    ///                * *
    ///               *  *
    ///              *   *
    ///             3    *
    ///          *       *
    ///       *          * 
    ///    *             *
    /// 0  *  *  *  *  * 1
    /// </code>
    /// </summary>
    private static bool IsEar(Vector2d a, Vector2d b, Vector2d c, List<Vector2d> polygon)
    {
        foreach (Vector2d p in polygon)
        {
            if (p.Equals(a) || p.Equals(b) || p.Equals(c))
                continue;

            if (IsPointInTriangle(p, a, b, c))
                return false;
        }
        return true;
    }

    /// <summary>
    /// 判断点 p 是否在三角形 (a,b,c) 中, 在边或点上也算在三角形中<br/>
    /// 原理是: 假设 a->b->c 是顺时针, 那么
    /// <list type="bullet">
    /// <item>a->b->p</item>
    /// <item>b->c->p</item>
    /// <item>c->b->p</item>
    /// </list>也都必须是顺时针,否则就不在三角形中
    /// </summary>
    private static bool IsPointInTriangle(Vector2d p, Vector2d a, Vector2d b, Vector2d c)
    {
        var cross_abc = Util.Cross(a, b, c);
        if (cross_abc == 0)
        {
            //不是三角形
            return Util.IsNearlyPointOnLineSegment(p, new LineSegment2d(a, b), 0) && Util.IsNearlyPointOnLineSegment(p, new LineSegment2d(a, c), 0);
        }
        var cross_abp = Util.Cross(a, b, p);
        var cross_bcp = Util.Cross(b, c, p);
        var cross_cap = Util.Cross(c, a, p);
        if ((cross_abc > 0 && cross_abp >= 0 && cross_bcp >= 0 && cross_cap >= 0)
            || (cross_abc < 0 && cross_abp <= 0 && cross_bcp <= 0 && cross_cap <= 0))
            return true;
        return false;
    }
}
